package main

import (
	"fmt"
)

// 小孩结构体
type Boy struct {
	No   int  // 编号
	Next *Boy // 指向下一个小孩的指针，默认值是 nil。
}

// 编写一个函数，构成单向的环形链表
// num ：表示小孩的个数。
// *Boy ：返回该环形的链表的第一个小孩的指针。
func AddBoy(num int) *Boy {
	first := &Boy{}  // 空结点
	curBoy := &Boy{} // 空结点
	// 判断
	if num < 1 {
		fmt.Println("num的值不对")
		return first
	}
	// 循环的构建这个环形链表
	for i := 1; i <= num; i++ {
		boy := &Boy{
			No: i,
		}
		// 构成循环链表，需要一个辅助指针
		// 第一个小孩特殊处理
		if i == 1 { // 第一个小孩
			first = boy // fisrt 不动
			curBoy = boy
			curBoy.Next = first //
		} else {
			curBoy.Next = boy
			curBoy = boy
			curBoy.Next = first // 构造环形链表
		}
	}
	return first
}

// 显示单向的环形链表：遍历
func ShowBoy(first *Boy) {
	// 环形链表为空的情况
	if first.Next == nil {
		fmt.Println("链表为空，没有小孩...")
		return
	}
	// 创建一个指针，帮助遍历，走到这里，说明至少有一个小孩
	curBoy := first
	for {
		fmt.Printf("小孩编号=%d ->", curBoy.No)
		// 退出的条件
		if curBoy.Next == first {
			break
		}
		// curBoy 移动到下一个位置
		curBoy = curBoy.Next
	}
}

// 出圈
func PlayGame(first *Boy, startNo int, countNum int) {
	// 1 空的链表单独的处理
	if first.Next == nil {
		fmt.Println("空的链表，没有小孩")
		return
	}
	// 2 辅助指针，帮助我们删除小孩
	tail := first
	// 3 让 tail 定位到环形链表的最后一个小孩，因为 tail 在删除小孩时需要使用到。
	for {
		if tail.Next == first { // 说明 tail 到了最后的小孩
			break
		}
		tail = tail.Next
	}
	// 4 让 first 移动到 startNo 位置，tail 紧随其后
	for i := 1; i <= startNo-1; i++ {
		first = first.Next
		tail = tail.Next
	}
	fmt.Println()
	// 5 开始数 countNum, 然后就删除 first 指向的小孩
	for {
		// 开始数 countNum-1 次
		for i := 1; i <= countNum-1; i++ {
			first = first.Next
			tail = tail.Next
		}
		fmt.Printf("小孩编号为%d 出圈 \n", first.No)
		// 删除 first 指向的小孩
		first = first.Next
		tail.Next = first
		// 如果 tail == first, 圈子中只有一个小孩.
		if tail == first {
			break
		}
	}
	fmt.Printf("小孩编号为%d 出圈 \n", first.No)

}

func main() {
	first := AddBoy(30)
	// 显示
	ShowBoy(first)
	PlayGame(first, 20, 8)
}
